In a network including a loop structure, so-called deadlock sometimes occurs in which packets may not be exchanged. The deadlock occurs due to the buffer dependency of switches connected to each other in a network.
FIG. 41 is a diagram illustrating a mechanism of deadlock occurrence. In FIG. 41, S1, S2, S3, and S4 denote switches. In FIG. 41, B1, B2, B3, and B4 denote buffers. In FIG. 41, Pa1, Pa2, Pa3, and Pa4 denote packets. For example, in a network illustrated in FIG. 41, it is supposed that a packet is transmitted clockwise from switch to switch diagonally positioned. In this case, for example, when the packets are simultaneously transmitted from the respective switches, the packets are stored in the buffers of the switches adjacent clockwise to each other. For example, the packet Pa2 transmitted from the switch S1 to the destination switch S3 is stored in the buffer B2 of the switch S2. In addition, the packet Pa3 transmitted from the switch S2 to the destination switch S4 is stored in the buffer B3 of the switch S3. In addition, the packet Pa4 transmitted from the switch S3 to the destination switch S1 is stored in the buffer B4 of the switch S4. In addition, the packet Pa1 transmitted from the switch S4 to the destination switch S2 is stored in the buffer B1 of the switch S1.
Here, the buffer B3 of the switch S3 stores the packet Pa3 transmitted from the switch S2 toward the destination switch S4. In this case, the buffer B3 of the switch B3 has to be empty so that the packet Pa2 can be transmitted from the switch S2 to the switch S3. For such a reason, the switch S2 may not transmit the packet Pa2, which has been transmitted from the switch S1 toward the destination switch S3, to the switch S3. Likewise, since the packet may not be transmitted even from all the switches S1, S3, and S4, a packet transmission disabled state, that is, deadlock occurs in the network illustrated in FIG. 41. As such, enablement and disablement of transmission of a packet is determined based on the emptiness of a buffer of a packet destination switch. This is called buffer dependency. In addition, as illustrated in FIG. 41, the packet transmission disabled state occurred in a network due to the buffer dependency is called buffer dependency circulation.
The above-described buffer dependency can conceptually be expressed with a term “turn”. The turn is defined as a combination of ports of a switch transmitting an input packet to a destination. For example, the turn is defined as a combination of an input port to which a packet is input and an output port from which the input packet is output to a destination. For example, the turn which is a combination of the input port and the output port of the switch S2 illustrated in FIG. 41 is defined as “S1→S2→S3”. In order to make it possible for the packet Pa2 to be transmitted from the switch S2 to the switch S3, the buffer dependency in which the buffer B3 of the switch S3 has to be empty has a one-to-one correspondence relationship with “S1→S2→S3”.
FIG. 42 is a diagram illustrating a correspondence relationship between the buffer dependency circulation and a turn loop. In FIG. 42, 42-1 denotes buffer dependency circulation. In FIG. 42, (1) of 42-1 denotes buffer dependency in which the buffer B3 has to be empty in order to make it possible for the packet to be transmitted from the switch S2. In FIG. 42, (2) of 42-1 denotes buffer dependency in which the buffer B4 has to be empty in order to make it possible for the packet to be transmitted from the switch S3. In FIG. 42, (3) of 42-1 denotes buffer dependency in which the buffer B1 has to be empty in order to make it possible for the packet to be transmitted from the switch S4. In FIG. 42, (4) of 42-1 denotes buffer dependency in which the buffer B2 has to be empty in order to make it possible for the packet to be transmitted from the switch S1. In addition, as indicated by 42-1 of FIG. 42, the buffer dependency (1) to the buffer dependency (4) make a cycle in the network.
In FIG. 42, 42-2 denotes a turn loop. In FIG. 42, (1) of 42-2 denotes a turn formed by the switch S2 outputting the packet, which has been input from the switch S1, to the switch S3. In FIG. 42, (2) of 42-2 denotes a turn formed by the switch S3 outputting the packet, which has been input from the switch S2, to the switch S4. In FIG. 42, (3) of 42-2 denotes a turn formed by the switch S4 outputting the packet, which has been input from the switch S3, to the switch S1. In FIG. 42, (4) of 42-2 denotes a turn formed by the switch S1 outputting the packet, which has been input from the switch S4, to the switch S2. In addition, as indicated by 42-2 of FIG. 42, a loop goes round clockwise in the network when the turns (1) to (4) are linked to each other.
Accordingly, since the buffer dependency and the turn are said to have a one-to-one correspondence relationship with each other, (1) illustrated in 42-1 of FIG. 42 and (1) illustrated in 42-2 of FIG. 42 have a one-to-one correspondence relationship with each other. Moreover, (2) illustrated in 42-1 of FIG. 42 and (2) illustrated in 42-2 of FIG. 42 have a one-to-one correspondence relationship with each other. Likewise, (3) illustrated in 42-1 of FIG. 42 and (3) illustrated in 42-2 of FIG. 42 have a one-to-one correspondence relationship with each other and (4) illustrated in 42-1 of FIG. 42 and (4) illustrated in 42-2 of FIG. 42 have a one-to-one correspondence relationship with each other. Accordingly, the buffer dependency circulation illustrated in 42-1 of FIG. 42 is said to be conceptually equivalent to the turn loop illustrated in 42-2 of FIG. 42.
The above-described deadlock occurs due to the buffer dependency circulation, that is, the turn loop. Accordingly, there are known techniques for restricting a packet transmission direction to prevent the deadlock. For example, an “Up/down method” or a “turn Prohibition (TP) method” prevents the deadlock by determining prohibition turns to restrict packet transmission and transmitting packets along a routine from which the prohibition turns are excluded.
The determination of the prohibition turns according to the Up/down method will be described with reference to FIG. 43. FIG. 43 is a diagram illustrating the flow of the determination of the prohibition turns according to the Up/down method. According to the Up/down method, as illustrated in FIG. 32, in step S101, on a network including individual switches, which are allowable by the network, and links, which connect the switches to each other, the switch to be on the top in a network graph is determined. The switch determination method includes a method of selecting switches to which the minimum ID is allocated, a method of selecting switches at random, and a method of selecting switches equally distant from an end node. According to the Up/down method, the number of pops is determined in step S102 and an up direction is determined in step S103, as illustrated in FIG. 43. According to the Up/down method, the prohibition turns are determined in step S104, as illustrated in FIG. 43. For example, according to the Up/down method, when the transmission direction of an input packet is oriented from a down direction to an up direction, the turn corresponding to the transmission direction is determined as the prohibition turn so as to restrict the transmission direction.
FIG. 44 is a diagram illustrating a prohibition turn determination process according to the Up/down method. In step S102 described above with reference to FIG. 43, the number of pops of each switch is calculated as follows. That is, as illustrated in FIG. 44, the number of pops of the switch determined as the top switch in step S101 is assumed to be “0” in step S102. In addition, as illustrated in FIG. 44, the number of pops of the switch connected to the top switch with zero “0” pop is assumed to be “1” in step S102. In addition, as illustrated in FIG. 44, the number of pops of the switch connected to the switch with one “1”) pop is assumed to be “2” in step S102. In addition, the number of pops of the switch connected to the switch with two “2” pops is assumed to be “3” in step S102. In step S103, the direction oriented from the switch with the larger number of pops to the switch with the smaller number of pops is the up direction. On the contrary, a reverse direction to the up direction is the down direction. Among the switches with the same number of pops, either of the directions is determined as the up direction and the reverse direction thereto is determined as the down direction. As illustrated in FIG. 44, turns T1, T2, T3, and T4 in which the transmission direction is oriented from the down direction to the up direction are determined as the prohibition turns. Moreover, both directions indicated by the arrows of the turns T1, T2, T3, and T4 become the prohibition turns.
The determination of the prohibition turn according to the TP method will be described with reference to FIG. 45. FIG. 45 is a flowchart illustrating the flow of the determination of the prohibition turns according to the TP method. As illustrated in FIG. 45, the switch with the minimum order number on the network graph, that is, the minimum number of connection links is selected in step S201, the prohibition turn is determined in step S202, and then the switch selected in step S201 is deleted in step S203. In the TP method, the process returns to step S201 described above, the switch with the minimum number of connection links on the network graph is selected after the deletion of the switch, and then the above-described process is executed. In the TP method, the processes illustrated in FIG. 45 are repeated until all of the switches forming the turn are deleted.
FIG. 46 is a diagram illustrating the prohibition turn determination process according to the TP method. In the TP method, as indicated by 46-1 of FIG. 46, a switch N7 with the minimum number of connection links is selected and the switch N7 is deleted without determination of a turn since there is no turn formed by the switch N7. Subsequently, in the TP method, as indicated by 46-2 of FIG. 46, a switch N6 with the minimum number of connection links is selected, a prohibition turn T1 is determined, and then the switch N6 is deleted. Subsequently, in the TP method, as indicated by 46-3 of FIG. 46, a switch N3 with the minimum number of connection links is selected and the switch N3 is deleted without determination of a turn since there is no turn formed by the switch N3. Subsequently, in the TP method, as indicated by 46-4 of FIG. 46, a switch N2 is selected between the switch N2 and a switch N4 with the minimum number of connection links, a prohibition turn T2 is determined, and then the switch N2 is deleted. Subsequently, in the TP method, as indicated by 46-5 of FIG. 46, a switch N5 is selected among a switch N1, a switch N4, and a switch N5 with the minimum number of connection links, a prohibition turn T3 is determined, and then the switch N5 is deleted. Subsequently, in the TP method, as indicated by 46-6 of FIG. 46, the switch N4 is selected between the switch N1 and the switch N4 with the minimum number of connection links and the switch N4 is deleted without determination of a turn since there is no turn formed by the switch N4. Thus, since only the switch N1 remains and there is no switch forming a turn, the prohibition turn determination process ends in the TP method and the turns T1, T2, and T3 are determined as the prohibition turns.
Examples of the related art are “Autonet: A High-speed, Self-Configuring Local Area Network Using Point-to-Point Links” Michael D. Schroeder, Andrew D. Birrell, Michael Burrows, Hal Murray, Roger M. Needham, Thomas L. Rodeheffer, Edwin H. Satterthwaite, Charles P. Thacker, IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 9, NO. 8, OCTOBER 1991; and “Application of network calculus to general topologies using turn-prohibition”, David Starobinski, Mark Karpovsky, Lev A. Zakrevski, IEEE/ACM Transactions on Networking (TON) archive Volume 11, Issue 3 (June 2003) table of contents, Pages: 411-421, Year of Publication: 2003, ISSN: 1063-6692.
However, the above-described techniques restricting the packet transmission direction have a problem that the communication amounts of respective links may not efficiently be distributed when a routing is executed in consideration of the prohibition turns.
FIG. 47 is a diagram illustrating an example of the communication amounts of respective links forming a network. When the communication amount of the turn passing clockwise through the switch S2 is “10”, as illustrated in FIG. 47, the communication amount of link corresponding to this turn is “11”. When the communication amount of the turn passing clockwise through the switch S3 is “1”, as illustrated in FIG. 47, the communication amount of link corresponding to this turn is “11”. When the communication amount of turn passing clockwise through the switch S4 is “10”, as illustrated in FIG. 47, the communication amount of link corresponding to this turn is “11”. When the communication amount of turn passing clockwise through the switch S1 is “1”, as illustrated in FIG. 47, the communication amount of link corresponding to this turn is “11”.
FIG. 48 is a diagram illustrating comparison between the communication amounts of respective links according to a difference between the prohibition turns. In FIG. 48, 48-1 denotes the communication amounts of respective links when a turn BT1 passing clockwise through the switch S3 and routing is executed so as to detour this prohibition turn counterclockwise. In other words, 48-1 denotes the communication amounts of respective links when a turn “S2→S3→S4” passing clockwise through the switch S3 is set as a prohibition turn and routing is executed along a turn “S2→S1→S4” to detour this prohibition turn counterclockwise. In FIG. 48, 48-2 denotes the communication amounts of respective links when a turn BT2 passing clockwise through the switch S3 and routing is executed so as to detour this prohibition turn counterclockwise. In other words, 48-2 denotes the communication amounts of respective links when a turn “S1→S2→S3” passing clockwise through the switch S3 is set as a prohibition turn and routing is executed along a turn “S1→S4→S3” to detour this prohibition turn counterclockwise.
FIG. 49 is a diagram illustrating the details of the communication amounts of respective links after routing is executed so as to detour a prohibition turn. Here, 49-1 illustrated in FIG. 49 corresponds to 48-1 illustrated in FIG. 48. Here, 49-2 illustrated in FIG. 49 corresponds to 48-2 illustrated in FIG. 48. As illustrated in 48-1 of FIG. 48 or 49-1 of FIG. 49, the communication amount of link is “12” or “10” when the routing is executed so as to detour the prohibition turn BT1 counterclockwise. As illustrated in 48-2 of FIG. 48 or 49-2 of FIG. 49, the communication amount of link is “21” or “1” when the routing is executed so as to detour the prohibition turn BT2 counterclockwise. Accordingly, it can be understood that after the routing is executed along a turn to detour the prohibition turn, the communication amounts of respective links are more efficiently distributed in 48-1 illustrated in FIG. 48 than in 48-2 illustrated in FIG. 48. However, as in the above-described Up/down method and the TP method, with the technique for determining the prohibition turn and restricting the packet transmission direction, the prohibition turn may not be determined so as to use turns along which the communication amounts of respective links are distributed. Accordingly, the technique for restricting the packet transmission direction has the problem in that the communication amount may not be efficiently distributed when routing is executed so as to prevent the deadlock in a network.